package org.leetcode.easy.leetcode206;

import org.leetcode.easy.ListNode;


public class Solution
{

    class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val=val;
            this.next=null;
        }

        public ListNode(int val,ListNode next){
            this.val=val;
            this.next=next;
        }
    }

    public ListNode reverseList5(ListNode node){

        if (node==null){
            return null;
        }

        ListNode pre = null;
        ListNode curr = node;
        ListNode next = null;
        while (curr!=null){
            next=curr.next;
            curr.next=pre;
            pre=curr;
            curr=next;
        }

        return pre;
    }
    public ListNode reverseList(ListNode node) {

        if (node==null)
        {
            return node;
        }


        ListNode pre=null;

        ListNode cur =node;

        //用来存储cur的下个节点
        ListNode temp=null;

        while (cur!=null)
        {
            temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }

        return pre;
    }


    /**
     * 递归
     */
    public ListNode reverseList1(ListNode node)
    {
        return reverse(null,node);
    }


    private ListNode reverse(ListNode pre,ListNode cur)
    {
        if (cur==null)
        {
            return pre;
        }


        ListNode temp = null;

        temp=cur.next;

        cur.next=pre;

        //下面的两行代码可以简化为 return reverse(cur,temp);
        pre =cur;
        cur =temp;

        return reverse(pre,cur);
    }




    /**
     * 第二次编写
     * @param node
     * @return
     */
    public ListNode reverseList2(ListNode node)
    {
        if (node==null)
        {
            return node;
        }

        ListNode pre = null;
        ListNode curr=node;

        ListNode temp = null;

        while (curr!=null) {
            temp=curr.next;
            curr.next=pre;
            pre=curr;
            curr=temp;
        }

        return pre;
    }




    public static void main(String[] args) {

//        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, null))));
//
//        Solution solution = new Solution();
//
//        ListNode listNode1 = solution.reverseList(listNode);

    }

}
